////////////////////////////////////////    string类型快读快写          /////////////////////////////
string read_str() {
	char ch=getchar();
	while (ch==' '||ch=='\n'||ch=='\r') {
		ch=getchar();
	}

	string s;
	while (ch!=' '&&ch!='\n'&&ch!='\r'&&ch!=EOF) {
		s+=ch;
		ch=getchar();
	}
	return s;
}

void print_str(string &str) {
	for (char ch:str) {
		putchar(ch);
	}
}
//////////////////////////////////////////   long long快读和快写       /////////////////////////////
long long read_ll() { //快速读取长整型
	char ch=getchar();
	while (!isdigit(ch)&&ch!='-') {
		ch=getchar();
	}

	long long x=0,f=1;
	if (ch=='-') {
		f=-1;
		ch=getchar();
	}

	while (isdigit(ch)) {
		x=x*10+ch-'0';
		ch=getchar();
	}

	return x*f;
}

void print_ll(long long x) { //快速输出长整型
	if (x==0) {
		putchar('0');
		return;
	}
	if (x<0) {
		putchar('-');
		x=-x;
	}

	deque<char> s;
	while (x>0) {
		s.push_front(x%10+'0');
		x/=10;
	}

	while (!s.empty()) {
		putchar(s.front());
		s.pop_front();
	}

	return;
}
//////////////////////////////////////////    大整形的快读快写    /////////////////////////////////////////////////
__int128 read_int128() { //大整形快读
	char ch=getchar();

	while (!isdigit(ch)&&ch!='-') ch=getchar();
	__int128 ans=0;
	__int128 f=1;
	if (ch=='-') {
		f=-1;
		ch=getchar();
	}

	while (isdigit(ch)) {
		ans=ans*10+ch-'0';
		ch=getchar();
	}

	return ans*f;
}

void print_int128(__int128 x) { //大整形快写
	if (x==0) {
		putchar('0');
		return;
	}
	
	if (x<0) putchar('-'),x=-x;

	deque<char> s;
	while (x>0) {
		s.push_front(x%10+'0');
		x/=10;
	}

	while (!s.empty()) {
		putchar(s.front());
		s.pop_front();
	}
}